package treeStudy;

import common.utils.TreeNode;

public class TreeStudy01 {

    /**
     * 根据前序中序结果构造树，递归的应用
     * @param args
     */
    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in = {4,7,2,1,5,3,8,6};
        TreeNode treeNode = recreateTree(pre, in);
        preOrder(treeNode);

    }

    //树的前序遍历
    public static void preOrder(TreeNode t){
        if (t == null) return;
        System.out.println(t.val);
        preOrder(t.left);
        preOrder(t.right);
    }

    public static TreeNode recreateTree(int[] pre, int[] in){
        return recreateTree(pre, in, 0, pre.length-1, 0, in.length-1);
    }

    public static TreeNode recreateTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
        //定义递归出口
        if (preStart > preEnd || inStart > preEnd){
            return null;
        }
        //定义出根节点
        TreeNode root = new TreeNode(pre[preStart]);
        int inPosition = inStart;
        for (int i = inStart; i <= inEnd; i++ ){
            if (in[i] == pre[preStart]){
                inPosition = i;
                break;
            }
        }
        //左子树节点的数量
        int leftTreeNodes = inPosition - inStart;
        //右子树节点数量
        int rightTreeNodes = inEnd - inPosition;

        root.left = recreateTree(pre, in, preStart+1, preStart + leftTreeNodes, inStart, inPosition-1);
        root.right = recreateTree(pre, in, preStart + leftTreeNodes+1, preEnd, inPosition+1, inEnd);

        return root;
    }
}
